(0) Obligation:
The Runtime Complexity (innermost) of the given
CpxTRS could be proven to be
BOUNDS(1, n^1).
The TRS R consists of the following rules:
a__f(f(X)) → a__c(f(g(f(X))))
a__c(X) → d(X)
a__h(X) → a__c(d(X))
mark(f(X)) → a__f(mark(X))
mark(c(X)) → a__c(X)
mark(h(X)) → a__h(mark(X))
mark(g(X)) → g(X)
mark(d(X)) → d(X)
a__f(X) → f(X)
a__c(X) → c(X)
a__h(X) → h(X)
Rewrite Strategy: INNERMOST
(1) CpxTrsMatchBoundsProof (EQUIVALENT transformation)
A linear upper bound on the runtime complexity of the TRS R could be shown with a Match Bound [MATCHBOUNDS1,MATCHBOUNDS2] of 3.
The certificate found is represented by the following graph.
Start state: 1
Accept states: [2]
Transitions:
1→2[a__f_1|0, a__c_1|0, a__h_1|0, mark_1|0, f_1|1, d_1|1, c_1|1, h_1|1, a__c_1|1, g_1|1, d_1|2, c_1|2]
1→3[a__c_1|1, d_1|2, c_1|2]
1→6[a__c_1|1, d_1|2, c_1|2]
1→7[a__f_1|1, f_1|2]
1→8[a__h_1|1, h_1|2]
1→9[a__c_1|2, d_1|3, c_1|3]
1→10[a__c_1|2, d_1|3, c_1|3]
2→2[f_1|0, g_1|0, d_1|0, c_1|0, h_1|0]
3→4[f_1|1]
4→5[g_1|1]
5→2[f_1|1]
6→2[d_1|1]
7→2[mark_1|1, a__c_1|1, g_1|1, d_1|1, d_1|2, c_1|2]
7→7[a__f_1|1, f_1|2]
7→8[a__h_1|1, h_1|2]
7→9[a__c_1|2, d_1|3, c_1|3]
7→10[a__c_1|2, d_1|3, c_1|3]
8→2[mark_1|1, a__c_1|1, g_1|1, d_1|1, d_1|2, c_1|2]
8→7[a__f_1|1, f_1|2]
8→8[a__h_1|1, h_1|2]
8→9[a__c_1|2, d_1|3, c_1|3]
8→10[a__c_1|2, d_1|3, c_1|3]
9→8[d_1|2]
10→11[f_1|2]
11→12[g_1|2]
12→7[f_1|2]
(2) BOUNDS(1, n^1)
(3) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)
Converted Cpx (relative) TRS to CDT
(4) Obligation:
Complexity Dependency Tuples Problem
Rules:
a__f(f(z0)) → a__c(f(g(f(z0))))
a__f(z0) → f(z0)
a__c(z0) → d(z0)
a__c(z0) → c(z0)
a__h(z0) → a__c(d(z0))
a__h(z0) → h(z0)
mark(f(z0)) → a__f(mark(z0))
mark(c(z0)) → a__c(z0)
mark(h(z0)) → a__h(mark(z0))
mark(g(z0)) → g(z0)
mark(d(z0)) → d(z0)
Tuples:
A__F(f(z0)) → c1(A__C(f(g(f(z0)))))
A__F(z0) → c2
A__C(z0) → c3
A__C(z0) → c4
A__H(z0) → c5(A__C(d(z0)))
A__H(z0) → c6
MARK(f(z0)) → c7(A__F(mark(z0)), MARK(z0))
MARK(c(z0)) → c8(A__C(z0))
MARK(h(z0)) → c9(A__H(mark(z0)), MARK(z0))
MARK(g(z0)) → c10
MARK(d(z0)) → c11
S tuples:
A__F(f(z0)) → c1(A__C(f(g(f(z0)))))
A__F(z0) → c2
A__C(z0) → c3
A__C(z0) → c4
A__H(z0) → c5(A__C(d(z0)))
A__H(z0) → c6
MARK(f(z0)) → c7(A__F(mark(z0)), MARK(z0))
MARK(c(z0)) → c8(A__C(z0))
MARK(h(z0)) → c9(A__H(mark(z0)), MARK(z0))
MARK(g(z0)) → c10
MARK(d(z0)) → c11
K tuples:none
Defined Rule Symbols:
a__f, a__c, a__h, mark
Defined Pair Symbols:
A__F, A__C, A__H, MARK
Compound Symbols:
c1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11
(5) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)
Removed 9 trailing nodes:
A__C(z0) → c3
MARK(d(z0)) → c11
A__C(z0) → c4
A__F(f(z0)) → c1(A__C(f(g(f(z0)))))
MARK(c(z0)) → c8(A__C(z0))
A__H(z0) → c5(A__C(d(z0)))
A__H(z0) → c6
MARK(g(z0)) → c10
A__F(z0) → c2
(6) Obligation:
Complexity Dependency Tuples Problem
Rules:
a__f(f(z0)) → a__c(f(g(f(z0))))
a__f(z0) → f(z0)
a__c(z0) → d(z0)
a__c(z0) → c(z0)
a__h(z0) → a__c(d(z0))
a__h(z0) → h(z0)
mark(f(z0)) → a__f(mark(z0))
mark(c(z0)) → a__c(z0)
mark(h(z0)) → a__h(mark(z0))
mark(g(z0)) → g(z0)
mark(d(z0)) → d(z0)
Tuples:
MARK(f(z0)) → c7(A__F(mark(z0)), MARK(z0))
MARK(h(z0)) → c9(A__H(mark(z0)), MARK(z0))
S tuples:
MARK(f(z0)) → c7(A__F(mark(z0)), MARK(z0))
MARK(h(z0)) → c9(A__H(mark(z0)), MARK(z0))
K tuples:none
Defined Rule Symbols:
a__f, a__c, a__h, mark
Defined Pair Symbols:
MARK
Compound Symbols:
c7, c9
(7) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID) transformation)
Removed 2 trailing tuple parts
(8) Obligation:
Complexity Dependency Tuples Problem
Rules:
a__f(f(z0)) → a__c(f(g(f(z0))))
a__f(z0) → f(z0)
a__c(z0) → d(z0)
a__c(z0) → c(z0)
a__h(z0) → a__c(d(z0))
a__h(z0) → h(z0)
mark(f(z0)) → a__f(mark(z0))
mark(c(z0)) → a__c(z0)
mark(h(z0)) → a__h(mark(z0))
mark(g(z0)) → g(z0)
mark(d(z0)) → d(z0)
Tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
S tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
K tuples:none
Defined Rule Symbols:
a__f, a__c, a__h, mark
Defined Pair Symbols:
MARK
Compound Symbols:
c7, c9
(9) CdtUsableRulesProof (EQUIVALENT transformation)
The following rules are not usable and were removed:
a__f(f(z0)) → a__c(f(g(f(z0))))
a__f(z0) → f(z0)
a__c(z0) → d(z0)
a__c(z0) → c(z0)
a__h(z0) → a__c(d(z0))
a__h(z0) → h(z0)
mark(f(z0)) → a__f(mark(z0))
mark(c(z0)) → a__c(z0)
mark(h(z0)) → a__h(mark(z0))
mark(g(z0)) → g(z0)
mark(d(z0)) → d(z0)
(10) Obligation:
Complexity Dependency Tuples Problem
Rules:none
Tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
S tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
K tuples:none
Defined Rule Symbols:none
Defined Pair Symbols:
MARK
Compound Symbols:
c7, c9
(11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^2)) transformation)
Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S.
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
We considered the (Usable) Rules:none
And the Tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
The order we found is given by the following interpretation:
Polynomial interpretation :
POL(MARK(x1)) = x1 + x12
POL(c7(x1)) = x1
POL(c9(x1)) = x1
POL(f(x1)) = [1] + x1
POL(h(x1)) = [1] + x1
(12) Obligation:
Complexity Dependency Tuples Problem
Rules:none
Tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
S tuples:none
K tuples:
MARK(f(z0)) → c7(MARK(z0))
MARK(h(z0)) → c9(MARK(z0))
Defined Rule Symbols:none
Defined Pair Symbols:
MARK
Compound Symbols:
c7, c9
(13) SIsEmptyProof (BOTH BOUNDS(ID, ID) transformation)
The set S is empty
(14) BOUNDS(1, 1)